ハッシュ探索 hash search
計算して格納位置を探す
search 探索
アルゴリズム Algorithms
規則性
がないData要素の
search 探索
の際
前提:
Data数 n
繰り返し回数 a
1.
線形探索 Linear search
時間計算量 time complexity
$ O(n)^{a}
空間計算量 space complexity
2.ハッシュ探索
時間計算量 time complexity
O(n)
空間計算量 space complexity
n
後で
search 探索
しやすいように，データを格納する段階で工夫
Hash Table ハッシュテーブル
データを格納する位置は
ハッシュ関数 hash function
を用いて計算する．
探索時はキー値に対してハッシュ関数を適用し，データの格納位置を特定する．
うまく行かない時
衝突 collision
,
シノニム synonym
格納先に先客がいる
解決策
チェイン法 chaining
同一の
Hash ハッシュ値
をもつ要素を
連結リスト Linked list 連想配列 辞書 object
で管理する
search 探索
hash search,
線形探索 Linear search
オープンアドレス法 open hashing
Hash Table ハッシュテーブル
の空き要素が見つかるまで
ハッシュ関数 hash function
を繰り返す
search 探索
hash search
Hash Table ハッシュテーブル
と
ハッシュ関数 hash function
の設計
衝突がまったく発生しない場合
ハッシュ表のデータの探索・追加・削除は
O(1)
の時間計算量
ハッシュ関数 hash function
によって添字を見つけるだけでほぼ処理が完了するため
ハッシュ表を大きくすれば衝突発生の確率を抑えられる
その場合，空の要素が
メモリ Memory
を無駄に占有することに
衝突を避けるために
ハッシュ表の大きさ以下の整数をなるべく偏ることなく一様に生成する
ハッシュ関数 hash function
が望ましい
ハッシュ表の容量には
素数 PrimeNumber
がよく用いられる．
問題
LeetCode Two Sum